Introduction to Machine Learning

Unit 15: KNN Regressor, Regression Trees, and Evaluation Metrics

Introduction

Welcome to Unit 15, where we transition from classification to regression problems.

Classification vs. Regression:

Aspect Classification Regression
Output Type Discrete labels Continuous values
Examples Spam detection, image classification House price prediction, temperature forecasting
Loss Functions Cross-entropy, Gini impurity MSE, MAE, RMSE
Evaluation Metrics Accuracy, Precision, Recall, F1, AUC-ROC RMSE, MAE, R²

This lecture covers:

Real-world Regression Examples:

  • Predicting house prices from size, location, and features
  • Estimating rainfall from weather sensor data
  • Forecasting stock prices or energy demand
  • Predicting student GPA from study hours and attendance
  • Estimating patient recovery time from medical measurements

Theory

From Classification to Regression

While classification and regression are different types of problems, they share a similar ML pipeline:

  1. Data collection
  2. Data preprocessing
    • Handle missing values, outliers
    • Feature scaling (critical for models using gradient descent)
    • Encoding (relevant for mixed features)
  3. Train-test split (or train-val-test)
  4. Model training
    • Choose algorithm (e.g., linear regression, regression trees, gradient boosting)
    • Optimize using regression-specific loss (e.g., MSE, MAE)
  5. Evaluation
    • Use regression metrics: RMSE, MAE, R²
    • Not classification metrics: accuracy, F1-score, AUC-ROC

Evaluation: How Do We Measure Regression Performance?

Unlike classification, which uses metrics like accuracy and F1-score, regression requires different evaluation metrics:

Common Regression Metrics:

1. Mean Squared Error (MSE)

\[ \text{MSE} = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{y}_i)^2 \]
  • Interpretation: Average squared difference between actual and predicted values
  • Penalty: Penalizes large errors heavily (due to squaring)
  • Units: (original units)² - can be hard to interpret
  • Use case: When large errors are particularly undesirable

2. Root Mean Squared Error (RMSE)

\[ \text{RMSE} = \sqrt{\text{MSE}} = \sqrt{\frac{1}{n} \sum_{i=1}^n (y_i - \hat{y}_i)^2} \]
  • Interpretation: Square root of average squared error
  • Advantage: Same units as the target variable → easier to interpret
  • Penalty: Still penalizes large errors heavily
  • Use case: Most common metric for regression, easy to interpret

3. Mean Absolute Error (MAE)

\[ \text{MAE} = \frac{1}{n} \sum_{i=1}^n |y_i - \hat{y}_i| \]
  • Interpretation: Average absolute error
  • Advantage: More robust to outliers than MSE/RMSE
  • Units: Same as target variable
  • Use case: When outliers are present and you want a robust metric

Choosing Between MSE, RMSE, and MAE:

Metric Sensitive to Outliers Interpretable Units Differentiable
MSE ✅ Yes (heavily) ❌ No (squared units) ✅ Yes
RMSE ✅ Yes (heavily) ✅ Yes (original units) ❌ No (due to square root)
MAE ❌ No (robust) ✅ Yes (original units) ❌ No (due to absolute value)

Regression Algorithms – Course Roadmap

This course will cover several regression algorithms:

  1. K-Nearest Neighbors (KNN) Regressor
    • Non-parametric, instance-based
    • Simple extension from KNN classification
  2. Regression Trees (Decision Trees)
    • Non-parametric, rule-based
    • Splits to minimize MSE
  3. Ordinary Least Squares (OLS) Regression
    • Parametric, linear model
    • Closed-form solution or gradient descent
  4. Polynomial Regression
    • Extending OLS for non-linear relationships
    • Feature engineering approach
  5. Regularized Regression (Ridge & Lasso)
    • OLS with shrinkage/penalty
    • Prevents overfitting, automatic feature selection
  6. Gradient Boosting for Regression
    • Ensemble method (combines multiple trees)
    • State-of-the-art performance

K-Nearest Neighbors (KNN) Regressor

Similar to K-NN classification, but instead of assigning a class label, K-NN regression predicts a continuous value by averaging the values of the k-nearest neighbors.

How KNN Regression Works:

  • For a given query point, identify the k-nearest neighbors
  • Compute the average (or weighted average) of their target values to get the prediction
  • Typically uses Euclidean distance (or others, such as Manhattan) to find the nearest neighbors
  • Often, closer neighbors are given higher weights in the averaging process to improve prediction accuracy

Characteristics:

  • Computationally expensive: With large datasets, especially as the number of features grows
  • Sensitive to choice of k: Small k can lead to noisy predictions, large k can oversmooth
  • Sensitive to distance metric: Different distance metrics can give different results
  • Works well for non-linear relationships: When the data distribution has local patterns rather than a global trend
  • No training phase: KNN is a lazy learner - it memorizes the training data

KNN Regression Example

Consider a dataset with TV, Radio, and Newspaper advertising budgets, and Sales as the target:

# TV Radio Newspaper Sales
R1230.137.869.2?
R244.539.345.110.4
R317.245.969.39.3
R4151.541.358.518.5
R5180.810.858.412.9
R68.748.9757.2

Example predictions:

KNN Regression Visualization A one-dimensional K-nearest neighbors regression example showing sales values, a query point at position 16, and predictions for K equal to 1, 3, and 5. KNN Regression Visualization Estimating sales for an unknown query position using nearby observations Sales values at different positions Observed points along a one-dimensional feature line 0 5 10 15 20 25 30 Query: 16 7 9 12 18 25 30 Position Sales Predict from nearby points Predictions by neighborhood size 1 K = 1 Nearest neighbor Position 15 · Sales 18 Prediction 18 direct estimate 3 K = 3 Nearest neighbors 10 (12) · 15 (18) · 20 (25) Average prediction 18.33 (12 + 18 + 25) / 3 5 K = 5 Nearest neighbors 5 (9) · 10 (12) · 15 (18) 20 (25) · 25 (30) Average prediction 18.8 (9 + 12 + 18 + 25 + 30) / 5 i Smoothing insight As K increases, more observations influence the estimate and the prediction becomes smoother.

Regression Tree

The decision tree method can also be used for numerical response variables. Regression trees operate in much the same fashion as classification trees, but with key differences:

Regression Trees vs Classification Trees:

Aspect Classification Trees Regression Trees
Target Variable Categorical Continuous
Leaf Node Value Majority class (voting) Average of training data in that leaf
Impurity Measure Gini impurity, Entropy Sum of squared deviations from the mean
Splitting Criterion Maximize information gain Minimize MSE (or variance)

Key Insight: In regression trees, the value of the leaf node is determined by the average of the training data that were in that leaf. A typical impurity measure is the sum of the squared deviations from the mean of the leaf.

Important Notes:

  • Data requirements: As with other data-driven methods, trees require large amounts of data
  • Overfitting: Regression trees are prone to overfitting (we'll discuss this more later)
  • Interpretability: One advantage of regression trees is that they are highly interpretable

Regression Tree Example

Consider a dataset for predicting the number of golf players based on weather conditions:

Day Outlook Temp. Humidity Wind Golf Players
1SunnyHotHighWeak25
2SunnyHotHighStrong30
3OvercastHotHighWeak46
4RainMildHighWeak45
5RainCoolNormalWeak52
6RainCoolNormalStrong23
7OvercastCoolNormalStrong43
8SunnyMildHighWeak35
9SunnyCoolNormalWeak38
10RainMildNormalWeak46
11SunnyMildNormalStrong48
12OvercastMildHighStrong52
13OvercastHotNormalWeak44
14RainMildHighStrong30

Now consider the same dataset with Temperature as a numeric predictor:

Day Outlook Temp. Humidity Wind Golf Players
1Sunny42HighWeak25
2Sunny38HighStrong30
3Overcast40HighWeak46
4Rain32HighWeak45
5Rain12NormalWeak52
6Rain14NormalStrong23
7Overcast15NormalStrong43
8Sunny28HighWeak35
9Sunny10NormalWeak38
10Rain24NormalWeak46
11Sunny22NormalStrong48
12Overcast26HighStrong52
13Overcast36NormalWeak44
14Rain30HighStrong30

Effect of Tree Depth:

  • With max_depth=2: The tree makes only a few cuts, resulting in a simpler, "step-like" prediction that may not capture finer variations in the data
  • With max_depth=3: More splits lead to a more complex tree that can better adapt to variations in the data
  • Trade-off:
    • Lower depth: Higher bias (simpler model, fewer splits)
    • Higher depth: Increases variance (more responsive to fluctuations in the data, risk of overfitting)

Overfitting in Regression Trees

Overfitting is a significant issue with regression trees:

Overfitting in Regression Trees Comparison of an overfit regression tree without regularization and a smoother regression tree with a minimum samples per leaf of ten. Overfitting in Regression Trees Regularization controls model complexity so predictions generalize beyond the training set Without Regularization Overfit model Prediction Training points Complex prediction path Observed data Result Complex, jagged predictions follow nearly every point—including noise. With Regularization min_samples_leaf = 10 Prediction Training points Regularized prediction Observed data Result Simpler, more reasonable model ignores noise and generalizes better. Key insight Without regularization, regression trees can create predictions that obviously overfit the training set.

Interactive Examples

MSE Calculation Example

Consider a house price prediction model with the following data:

House Price ($1000s) y Square Feet x
2451400
3121600
2791700
3081875
1991100
2191550
4052350
3242450
3191425
2551700

Imagine a model made the following predictions:

Actual (y) Square Feet (x) Predicted (ŷ) Error Error²
2451400252-749
3121600273.938.11451.61
2791700284.9-5.934.81
3081875304.13.915.21
1991100219-20400
2191550268.4-49.42440.36
4052350356.348.72371.69
3242450367.3-43.31874.89
3191425254.764.34134.49
2551700284.9-29.9894.01

Calculate MSE:

\[ \text{MSE} = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{y}_i)^2 = \frac{49 + 1451.61 + 34.81 + 15.21 + 400 + 2440.36 + 2371.69 + 1874.89 + 4134.49 + 894.01}{10} \] \[ = \frac{13176.07}{10} = 1317.607 \]

KNN Regression Visualization

Consider a simple 1D regression problem:

KNN Regression in One Dimension A visual explanation of K nearest neighbors regression for a query point at x equals 4.5, showing predictions for K values 1 through 4. KNN Regression in 1D Predicting a value by averaging the nearest observations QUERY POINT x = 4.5 Observed data and query location The nearest points are selected by horizontal distance from x = 4.5. 0 2 4 6 8 1 2 3 4 5 6 7 8 feature x target y x = 4.5 query How prediction works 1. Measure distance from the query to every observed point. 2. Select the K closest neighbors. 3. Average their target values: ŷ = average of neighbor y values DATASET x: 1, 2, 3, 4, 5, 6, 7, 8 y: 2, 4, 5, 4, 6, 8, 7, 9 Predictions for different values of K Increasing K smooths the estimate by including more nearby observations. K = 1 Nearest neighbor x=4, y=4 Prediction 4 K = 2 Nearest neighbors x=4, y=4 x=5, y=6 Prediction 5 (4 + 6) / 2 K = 3 Nearest neighbors x=3, y=5 x=4, y=4 x=5, y=6 Prediction ≈ 5 (5 + 4 + 6) / 3 K = 4 Nearest neighbors x=2,4 x=3,5 x=4,4 x=5,6 Prediction 4.75 (4 + 5 + 4 + 6) / 4

Numerical Solutions

MSE, RMSE, and MAE Calculation

Given the following actual and predicted values:

Actual (y) Predicted (ŷ) Error (y - ŷ) Error² |Error|
1012-242
1514111
2018242
2527-242
3028242

Calculate:

MSE: \[ \text{MSE} = \frac{4 + 1 + 4 + 4 + 4}{5} = \frac{17}{5} = 3.4 \]
RMSE: \[ \text{RMSE} = \sqrt{3.4} \approx 1.84 \]
MAE: \[ \text{MAE} = \frac{2 + 1 + 2 + 2 + 2}{5} = \frac{9}{5} = 1.8 \]

KNN Regression Calculation

Given the following data points (x, y):

(1, 2), (2, 4), (3, 5), (4, 4), (5, 6), (6, 8), (7, 7), (8, 9)

Query point: x = 4.5

Calculate predictions for different K values:

K = 1: \[ \text{Nearest neighbor: } (4, 4) \implies \text{Prediction} = 4 \]
K = 2: \[ \text{Nearest neighbors: } (4, 4), (5, 6) \implies \text{Prediction} = \frac{4 + 6}{2} = 5 \]
K = 3: \[ \text{Nearest neighbors: } (3, 5), (4, 4), (5, 6) \implies \text{Prediction} = \frac{5 + 4 + 6}{3} \approx 5 \]
K = 4: \[ \text{Nearest neighbors: } (2, 4), (3, 5), (4, 4), (5, 6) \implies \text{Prediction} = \frac{4 + 5 + 4 + 6}{4} = 4.75 \]

Try It Yourself

Problem 1: MSE and RMSE Calculation

Given the following actual and predicted values:

ActualPredicted
57
108
1516
2019

Tasks:

  1. Calculate MSE
  2. Calculate RMSE
  3. Which metric is easier to interpret and why?

Solution:

  1. Errors: (5-7)=-2, (10-8)=2, (15-16)=-1, (20-19)=1
  2. Squared errors: 4, 4, 1, 1
  3. MSE: (4 + 4 + 1 + 1)/4 = 10/4 = 2.5
  4. RMSE: √2.5 ≈ 1.58
  5. Interpretability: RMSE is easier to interpret because it's in the same units as the target variable (2.5 vs 1.58, where 1.58 is more meaningful)
Problem 2: MAE vs MSE

Given two models with the following errors on a test set:

Model A: Errors = [-3, -2, -1, 0, 1, 2, 3]

Model B: Errors = [-5, -1, -1, 0, 1, 1, 5]

Tasks:

  1. Calculate MAE for both models
  2. Calculate MSE for both models
  3. Which model performs better according to MAE?
  4. Which model performs better according to MSE?
  5. Which metric do you think is more appropriate here and why?

Solution:

  1. MAE:
    • Model A: (3+2+1+0+1+2+3)/7 = 12/7 ≈ 1.71
    • Model B: (5+1+1+0+1+1+5)/7 = 14/7 = 2.0
  2. MSE:
    • Model A: (9+4+1+0+1+4+9)/7 = 28/7 = 4.0
    • Model B: (25+1+1+0+1+1+25)/7 = 54/7 ≈ 7.71
  3. MAE winner: Model A (1.71 < 2.0)
  4. MSE winner: Model A (4.0 < 7.71)
  5. Appropriate metric: Both metrics agree that Model A is better. However, MSE penalizes Model B more heavily for its large errors (-5 and 5), which might be desirable if large errors are particularly bad. MAE is more robust to outliers.
Problem 3: KNN Regression Prediction

Given the following training data (x, y):

(1, 3), (2, 5), (3, 7), (4, 9), (5, 11)

Query point: x = 3.5

Tasks:

  1. What is the prediction when K=1?
  2. What is the prediction when K=2?
  3. What is the prediction when K=3?
  4. As K increases, what happens to the prediction?

Solution:

  1. K=1: Nearest neighbor is (3, 7) or (4, 9). Assuming Euclidean distance, both are equally close (distance=0.5). Typically, we'd pick the first one: Prediction = 7
  2. K=2: Nearest neighbors: (3, 7) and (4, 9). Prediction = (7 + 9)/2 = 8
  3. K=3: Nearest neighbors: (2, 5), (3, 7), (4, 9). Prediction = (5 + 7 + 9)/3 ≈ 7
  4. As K increases: The prediction becomes more smoothed and approaches the average of all y values (7). With K=5, prediction = (3+5+7+9+11)/5 = 7.
Problem 4: Regression Tree Splitting

Consider a simple dataset for predicting house prices based on square footage:

Square FeetPrice ($1000s)
1000200
1200220
1500250
1800300
2000320

Task: If we're building a regression tree with max_depth=1 (one split), where would be the optimal split point to minimize MSE? Calculate the MSE for splits at 1300, 1400, 1600, and 1700 square feet.

Solution:

For each potential split, we calculate the MSE of the predictions:

Split at 1300:

  • Left (≤1300): 1000(200), 1200(220) → mean = 210
  • Right (>1300): 1500(250), 1800(300), 2000(320) → mean = 290
  • MSE = [(200-210)² + (220-210)² + (250-290)² + (300-290)² + (320-290)²]/5
  • = [100 + 100 + 1600 + 100 + 900]/5 = 2800/5 = 560

Split at 1400:

  • Left (≤1400): 1000(200), 1200(220) → mean = 210
  • Right (>1400): 1500(250), 1800(300), 2000(320) → mean = 290
  • MSE = 560 (same as 1300)

Split at 1600:

  • Left (≤1600): 1000(200), 1200(220), 1500(250) → mean = 223.33
  • Right (>1600): 1800(300), 2000(320) → mean = 310
  • MSE = [(200-223.33)² + (220-223.33)² + (250-223.33)² + (300-310)² + (320-310)²]/5
  • = [537.78 + 11.11 + 711.11 + 100 + 100]/5 ≈ 1460/5 = 292

Split at 1700:

  • Left (≤1700): 1000(200), 1200(220), 1500(250), 1800(300) → mean = 242.5
  • Right (>1700): 2000(320) → mean = 320
  • MSE = [(200-242.5)² + (220-242.5)² + (250-242.5)² + (300-242.5)² + (320-320)²]/5
  • = [1806.25 + 506.25 + 56.25 + 3306.25 + 0]/5 = 5775/5 = 1155

Optimal split: At 1600 square feet with MSE = 292 (lowest MSE)

Problem 5: Choosing Evaluation Metric

You are building a model to predict house prices, and your dataset contains some outliers (very expensive houses that are unusual for their size).

Tasks:

  1. Which evaluation metric would you choose: MSE, RMSE, or MAE?
  2. Why is this metric more appropriate?
  3. If you want to heavily penalize large errors (e.g., underestimating the price of an expensive house by a lot), which metric would you choose?

Solution:

  1. Recommended metric: MAE (Mean Absolute Error)
  2. Reason: MAE is more robust to outliers. Since the dataset contains outliers (very expensive houses), MSE and RMSE would be heavily influenced by these extreme values, giving a distorted view of typical model performance. MAE treats all errors equally, regardless of their magnitude.
  3. For penalizing large errors: MSE or RMSE. Both heavily penalize large errors due to the squaring operation. RMSE is often preferred because it's in the same units as the target variable, making it more interpretable.

Interactive Quiz

Test your understanding of KNN Regressor, Regression Trees, and Evaluation Metrics:

Question 1: What is the main difference between classification and regression?

A) Classification predicts discrete labels, regression predicts continuous values
B) Classification uses trees, regression uses neural networks
C) Classification has more evaluation metrics than regression
D) Regression is always more accurate than classification

Question 2: Which metric is most sensitive to outliers?

A) MAE
B) MSE
C) RMSE
D) Both B and C

Question 3: In KNN regression, what happens to the prediction as K increases?

A) The prediction becomes more accurate
B) The prediction becomes more smoothed (less sensitive to individual points)
C) The prediction becomes more sensitive to noise
D) The prediction time decreases significantly

Question 4: In a regression tree, how is the value of a leaf node determined?

A) By the majority class of training samples in that leaf
B) By the average of the target values of training samples in that leaf
C) By the median of the target values of training samples in that leaf
D) By the mode of the target values of training samples in that leaf

Question 5: What is the primary issue with regression trees without regularization?

A) They are too simple and underfit the data
B) They are prone to overfitting the training data
C) They cannot handle numerical features
D) They require too much memory

Key Takeaways

Classification vs Regression:

  • Output type: Classification predicts discrete labels, regression predicts continuous values
  • Examples: Classification (spam detection, image classification), Regression (house price prediction, temperature forecasting)
  • ML pipeline: Similar pipeline for both: data → preprocessing → train-test split → model training → prediction
  • Key differences: Different loss functions, different evaluation metrics

Evaluation Metrics:

  • MSE (Mean Squared Error): Average squared difference, penalizes large errors heavily, units are squared
  • RMSE (Root Mean Squared Error): Square root of MSE, same units as target, penalizes large errors heavily
  • MAE (Mean Absolute Error): Average absolute difference, robust to outliers, same units as target

KNN Regressor:

  • Non-parametric: Makes no assumptions about the underlying data distribution
  • Instance-based: Uses the entire training dataset for predictions (lazy learning)
  • Prediction method: Averages (or weighted averages) of k-nearest neighbors' target values
  • Distance metric: Typically Euclidean, but can use others (Manhattan, etc.)
  • Strengths: Simple, works well for non-linear relationships with local patterns
  • Weaknesses: Computationally expensive, sensitive to choice of k and distance metric

Regression Trees:

  • Non-parametric: Makes no assumptions about the functional form
  • Rule-based: Creates a series of if-then rules based on feature thresholds
  • Leaf value: Average of training data in that leaf (unlike classification trees which use majority voting)
  • Splitting criterion: Minimizes MSE (or variance) of the resulting subsets
  • Strengths: Highly interpretable, can capture non-linear relationships, handles both numerical and categorical features
  • Weaknesses: Prone to overfitting, can be unstable (small data changes can lead to different trees)

General Insights:

  • Metric selection: Choose based on your priorities: MSE/RMSE for penalizing large errors, MAE for robustness to outliers
  • Model selection: KNN for local patterns, Regression Trees for interpretable non-linear relationships
  • Overfitting: Always a concern with flexible models like regression trees; use regularization or pruning
  • Feature importance: Regression trees naturally provide feature importance scores

Common Pitfalls

⚠️ Evaluation Metrics:

  • Using classification metrics: Never use accuracy, precision, recall, or F1-score for regression problems
  • Ignoring units: MSE has squared units, which can be misleading. RMSE is often more interpretable
  • Over-reliance on a single metric: Different metrics tell different stories. Use multiple metrics for a complete picture
  • Comparing metrics across scales: Metrics like MSE/RMSE/MAE are scale-dependent. Standardize or use relative metrics when comparing across different datasets

⚠️ KNN Regressor:

  • Choosing k: Too small k leads to noisy, overfit predictions; too large k leads to oversmoothed, high-bias predictions
  • Distance metric: Euclidean distance assumes spherical neighborhoods, which may not be appropriate for all data distributions
  • Feature scaling: Features must be scaled (standardized/normalized) when using Euclidean distance, otherwise features with larger scales will dominate
  • Computational cost: KNN can be slow for large datasets, especially in high dimensions
  • Curse of dimensionality: KNN performance degrades in high-dimensional spaces as all points become equally distant

⚠️ Regression Trees:

  • Overfitting: Regression trees can easily overfit the training data, creating trees that are too complex
  • No pruning: Without regularization (e.g., min_samples_leaf, max_depth), trees will grow until each leaf is pure or contains min_samples_split
  • Unstable: Small changes in the data can lead to very different tree structures
  • Biased towards dominant classes: In regions with few training samples, predictions may be unreliable
  • Extrapolation: Regression trees perform poorly on data outside the range of the training data
  • Feature importance bias: Trees tend to favor features with more possible split points (e.g., continuous over categorical)

⚠️ General:

  • Data leakage: Ensure that preprocessing (scaling for KNN) is done correctly within cross-validation folds
  • Ignoring assumptions: While tree-based methods make few assumptions, KNN assumes that nearby points have similar target values
  • Target variable distribution: Both KNN and regression trees assume that the target variable is roughly continuous in the input space

Resources

📚 KNN Regressor:

📚 Regression Trees:

📚 Evaluation Metrics:

📖 Books:

💻 Practical Implementation: